package J1_25;

import java.util.*;

public class test {
    public static class TreeNode {
        int val;

        TreeNode left;
        TreeNode right;

        public TreeNode(char x) {
            this.val = x;
        }
    }

    static int i = 0;
    //编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
    // 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
    // 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            TreeNode root =  createTree(in.next());
            inOrder(root);
            i = 0;
        }
    }

    public static TreeNode createTree(String str) {
        if (str.charAt(i) == '#') {
            i++;
            return null;
        }

        TreeNode root = new TreeNode(str.charAt(i));
        i++;
        root.left = createTree(str);
        root.right = createTree(str);


        return root;


    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val +" ");
        inOrder(root.right);
    }

    //给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new LinkedList<>();
            while (size != 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                tmp.add(node.val);
                size--;
            }
            list.add(tmp);
        }
        return list;
    }


    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
    // 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root == p || root == q) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);

        if (leftNode != null && rightNode != null) {
            return root;
        } else if (leftNode == null) {
            return rightNode;
        }

        return leftNode;


    }

}
